#include "TreeFactory.h"
#include "Node.h"
#include <list>
using std::list;

INode* TreeFactory::create(IFrequencyTable* table)
{
	list<Node*> treeList;
	table->reflesh();
	size_t numOfNodes = table->count();
	for( size_t i=0; i < numOfNodes; ++i)
    {
		treeList.push_back(new Node(table->getCurrentChar(),table->getCurrentNum()));
		table->moveIterator();
    }
            
	treeList.sort(compNodes());
	while(treeList.size() != 1)
    {
		Node* leftSon = treeList.front();
        treeList.pop_front();
		Node* rightSon = treeList.front();
        treeList.pop_front();

		Node* parent = new Node(leftSon,rightSon);
		list<Node*>::iterator i = treeList.begin();
		while((0 != treeList.size()) && (i._Ptr->_Myval->getNum() < parent->getNum()))		//ordered place
		{
			++i;
			if(treeList.end() == i)
				break;
		}

		treeList.insert(i,parent);
	}
	return treeList.front();
}